package algorithm_demo.demo01;

/**
 * 判断是否为平衡二叉树（AVL树）
 * 规则：
 *  一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
 * https://leetcode.cn/problems/balanced-binary-tree/
 *
 * @author Api
 * @date 2023/2/5 15:03
 */
public class Code32_BalancedBinaryTree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    public static boolean isBalanced(TreeNode root){
        return process(root).isBalanced;
    }


    public static Info process(TreeNode root){
        if (root == null){
            return new Info(true, 0);
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        //这里的1表示的是根节点的数量为1个
        int height = Math.max(leftInfo.height, rightInfo.height)+1;
        boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced && Math.abs(leftInfo.height- rightInfo.height)<2;
        return new Info(isBalanced, height);
    }
}
